Năm 468, Leo đã chọn Basiliscus làm thống soái đạo quân viễn chinh xâm chiếm Carthago. Cuộc xâm lược vương quốc của người Vandal là một trong những chiến dịch quân sự lớn nhất được ghi lại trong biên niên sử, một chiến dịch đổ bộ kết hợp với hơn mười ngàn tàu chiến và một trăm ngàn binh sĩ. Mục đích của chiến dịch này là để trừng phạt vua Geiseric của người Vandal vì đã mang quân cướp phá thành Roma vào năm 455, vốn là kinh đô cũ của Đế quốc Tây La Mã và cũng đã từng bị tàn phá vào năm 410, khiến Hoàng hậu Licinia Eudoxia (góa phụ của Hoàng đế Valentinianus III) cùng người con gái của bà bị quân rợ bắt làm con tin ngay khi thành bị chiếm.[1][4]

Kế hoạch này được sự phối hợp giữa Hoàng đế Đông La Mã Leo, Hoàng đế Tây La Mã Anthemius và Tướng Marcellinus, người hiện đang nắm quyền hành xứ Illyricum. Theo kế hoạch thì Basiliscus được lệnh dẫn hạm đội trực tiếp đến Carthago, trong khi Marcellinus dẫn quân tấn công và đánh chiếm Sardegna, riêng đội quân thứ ba dưới quyền thống soái của Heraclius xứ Edessa sẽ đổ bộ lên bờ biển phía đông Libya của Carthago và tiến hành đột kích. Có vẻ như các lực lượng phối hợp đã tập trung ở Sicilia, từ đó cả ba hạm đội sẽ di chuyển ở những thời điểm khác nhau.[4]

Các nhà sử học cổ đại và hiện đại đều có những ước tính khác nhau về số lượng tàu thuyền và binh sĩ dưới sự chỉ huy của Basiliscus, cũng như về các chi phí của cuộc viễn chinh. Nhìn chung cả hai đều có số lượng rất lớn; Nicephorus Gregoras nói có một trăm ngàn tàu chiến, Cedrenus đáng tin cậy hơn nói rằng hạm đội đã tấn công Carthago bao gồm một ngàn một trăm mười ba tàu chiến, cứ mỗi một tàu chở khoảng 100 người.[7] Chi phí của cuộc viễn chinh được ước tính vừa phải cũng tiêu tốn khoảng 64.000 lượng vàng, một số tiền đã vượt quá ngân khố triều đình trong một năm.[8]

Sardinia và Libya thì bị hai tướng Marcellinus và Heraclius chiếm được, khi Basiliscus bỏ neo ngoài khơi Promontorium Mercurii tại Cap Bon đối diện Sicilia, cách Carthago khoảng bốn mươi km. Geiseric phái ngưởi tới đề nghị Basiliscus cho phép ông có năm ngày để đưa ra các điều kiện cầu hòa.[9] Trong quá trình đàm phán, Geiseric tập hợp hạm đội của mình và bất ngờ tấn công hạm đội quân La Mã. Người Vandal đã chất đầy vật liệu dễ cháy lên nhiều tàu thuyền để tiến hành hỏa công. Suốt đêm đó, quân Vandal cho đẩy những chiếc thuyền bốc cháy đâm sầm vào chỗ hạm đội quân La Mã đang thả neo mà chẳng có phòng bị lẫn cảnh giác nào. Các tướng lĩnh Đông La Mã đã cố gắng giải cứu một số tàu khỏi bị lửa thiêu rụi nhưng việc ứng cứu đã bị ngăn cản từ hạm đội quân Vandal lúc này đang ra sức xông lên tiến công dữ dội.[4]

Basiliscus kịp thời trốn khỏi tâm điểm của trận chiến.[10] Một nửa hạm đội La Mã đã bị đốt cháy, đánh chìm, hoặc bị quân địch bắt giữ, riêng số còn lại đều rút theo Basiliscus. Toàn bộ cuộc viễn chinh đã thất bại thảm hại. Heraclius quyết định rút lui qua sa mạc tiến vào Tripolitania, chiếm giữ vị trí này được hai năm cho đến khi bị triệu về; Marcellinus rút quân về Sicilia, cũng là nơi mà Basiliscus đến trú tạm.[11] Tuy nhiên viên tướng này đã bị một trong số những viên hạm trưởng ám sát có lẽ là do sự xúi giục của Ricimer, điều này khiến vua Vandal tỏ ra ngạc nhiên và hài lòng của mình vì kể từ nay kẻ thù La Mã sẽ không bao giờ còn có thể đối chọi và đe dọa đến sự thống trị của người Vandal nữa.[4]

Sau khi trở về Constantinopolis, Basiliscus cùng đám thuộc hạ đã lén đến ẩn náu trong nhà thờ Hagia Sophia nhằm tránh cơn thịnh nộ của người dân và sự trừng phạt của Hoàng đế. Nhờ Verina làm trung gian hòa giải mà Basiliscus tạm thời được triều đình xá miễn tội chết và chỉ bị phạt bãi chức Đại tướng quân rồi lưu đày đến Heraclea Sintica ở Thracia.[12]